//给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i 
//+ 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [3,1,3,6]
//输出：false
// 
//
// 示例 2： 
//
// 
//输入：arr = [2,1,2,6]
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：arr = [4,-2,2,-4]
//输出：true
//解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= arr.length <= 3 * 10⁴ 
// arr.length 是偶数 
// -10⁵ <= arr[i] <= 10⁵ 
// 
// Related Topics 贪心 数组 哈希表 排序 👍 87 👎 0

package leetcode.editor.cn;

import java.util.*;

public class _954_ArrayOfDoubledPairs {
    public static void main(String[] args) {
        Solution solution = new _954_ArrayOfDoubledPairs().new Solution();
//        int[] arr = new int[] {4, -2, 2, -4};
        int[] arr = new int[] {2,4,0,0,8,1};
//        int[] arr = new int[] {3,1,3,6};
        System.out.println(solution.canReorderDoubled(arr));
    }

    class Solution {
        public boolean canReorderDoubled(int[] arr) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : arr) {
                // 这句话经典
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            if (map.getOrDefault(0, 0) % 2 != 0) return false;

            List<Integer> vals = new ArrayList<>();
            for (int x : map.keySet()) {
                vals.add(x);
            }
            Collections.sort(vals, (a, b) -> Math.abs(a) - Math.abs(b));

            for (int x : vals) {
                if (map.getOrDefault(2 * x, 0) < map.get(x)) {
                    return false;
                }
                map.put(2 * x, map.getOrDefault(2 * x, 0) - map.get(x));
            }
            return true;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 有错，0成了干扰，而且还有其他问题，主要集中在240081
    class Solution1 {
        public boolean canReorderDoubled(int[] arr) {
            Set<Integer> set = new HashSet<>();
            for (int num : arr) {
                if (set.contains(num / 2) || set.contains(2 * num)) {
                    if (set.contains(2 * num)) {
                        set.remove(2 * num);
                    } else if (num / 2 * 2 == num){
                        set.remove(num / 2);
                    }
                } else {
                    set.add(num);
                }
            }
            return set.isEmpty();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}